﻿#define _CRT_SECURE_NO_WARNINGS
//给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
//
//示例 1:
//
//输入: nums = [1, 2, 3, 4, 5, 6, 7], k = 3
//输出 : [5, 6, 7, 1, 2, 3, 4]
//解释 :
//    向右轮转 1 步 : [7, 1, 2, 3, 4, 5, 6]
//    向右轮转 2 步 : [6, 7, 1, 2, 3, 4, 5]
//    向右轮转 3 步 : [5, 6, 7, 1, 2, 3, 4]

//方法1
void rotate(int* nums, int numsSize, int k)
{
    void rotate(int* nums, int numsSize, int k)
    {
        k %= numsSize;
        int arr[numsSize];
        int i = 0;
        int j = 0;
        //需要轮转的元素放在数组前面
        for (i = numsSize - k; i < numsSize; i++)
        {
            arr[j] = nums[i];
            j++;
        }
        //剩余元素放到数组后面
        for (i = 0; i < numsSize - k; i++)
        {
            arr[j] = nums[i];
            j++;
        }
        //拷贝到原数组中
        j = 0;
        for (i = 0; i < numsSize; i++)
        {
            nums[j] = arr[i];
            j++;
        }
    }
}


//方法2
void reverse(int* start, int* end)
{
    while (start < end)
    {
        int tmp = *start;
        *start = *end;
        *end = tmp;
        start++;
        end--;
    }
}
void rotate(int* nums, int numsSize, int k)
{
    //向右轮转numsSize次相当于没轮转
    k %= numsSize;
    reverse(nums, nums + numsSize - 1 - k);
    reverse(nums + numsSize - k, nums + numsSize - 1);
    reverse(nums, nums + numsSize - 1);
}